//
// Created by francklinson on 2021/10/21 AT 10:35.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    int maxProductDifference(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return nums[n - 1] * nums[n - 2] - nums[0] * nums[1];
    }
};

class Solution2 { // 题解
public:
    int maxProductDifference(vector<int> &nums) {
        // 不用排序 只找4个数
        int n = nums.size();
        // 数组中最大的两个值
        int mx1 = max(nums[0], nums[1]);
        int mx2 = min(nums[0], nums[1]);
        // 数组中最小的两个值
        int mn1 = min(nums[0], nums[1]);
        int mn2 = max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            int tmp = nums[i];
            if (tmp > mx1) {
                mx2 = mx1;
                mx1 = tmp;
            } else if (tmp > mx2) {
                mx2 = tmp;
            }
            if (tmp < mn1) {
                mn2 = mn1;
                mn1 = tmp;
            } else if (tmp < mn2) {
                mn2 = tmp;
            }
        }
        return (mx1 * mx2) - (mn1 * mn2);
    }
};

int main() {
    vector<int> nums{4, 2, 5, 9, 7, 4, 8};
    Solution solution;
    cout << solution.maxProductDifference(nums) << endl;
    return 0;
}

